package com.neusoft.tree;

import lombok.Data;

import java.util.Objects;

/**
 * @author lichunlong lcl253137@alibaba-inc.com
 * @desc 二叉排序树
 * @date 2025-04-09
 */
@Data
public class BinarySortTree {

    /**
     * 根节点
     */
    private BinarySortNode rootNode;

    /**
     * 添加结点
     *
     * @param node 结点
     */
    public void add(BinarySortNode node) {
        if (Objects.isNull(rootNode)) {
            // 如果root为空, 则直接让root指向node
            rootNode = node;
        } else {
            rootNode.add(node);
        }
    }

    /**
     * 删除节点
     *
     * @param nodeValue 节点值
     */
    public void delete(int nodeValue) {
        if (Objects.isNull(rootNode)) {
            return;
        }
        // 1、先找到要删除的结点
        BinarySortNode toDeleteNode = rootNode.search(nodeValue);
        if (Objects.isNull(toDeleteNode)) {
            return;
        }
        // 如果当前的二叉排序树只有一个结点
        if (Objects.isNull(rootNode.getSubLeft()) && Objects.isNull(rootNode.getSubRight())) {
            rootNode = null;
            return;
        }
        // 2、找待删除节点的父结点
        BinarySortNode toDeleteParentNode = rootNode.searchParentNode(nodeValue);

        if (Objects.isNull(toDeleteNode.getSubLeft()) && Objects.isNull(toDeleteNode.getSubRight())) {
            /*
             * 要删除的结点是叶子结点
             *  判断待删除节点是父结点的左子结点，还是右子结点
             */
            if (Objects.nonNull(toDeleteParentNode.getSubLeft()) && nodeValue == toDeleteParentNode.getSubLeft().getItem()) {
                // 左子结点
                toDeleteParentNode.setSubLeft(null);
            } else if (Objects.nonNull(toDeleteParentNode.getSubRight()) && nodeValue == toDeleteParentNode.getSubRight().getItem()) {
                // 右子结点
                toDeleteParentNode.setSubRight(null);
            }
            return;
        }

        if (Objects.nonNull(toDeleteNode.getSubLeft()) && Objects.nonNull(toDeleteNode.getSubRight())) {
            // 删除有两颗子树的节点
            Integer minNodeValue = searchAndDeleteMinSubNodeValue((BinarySortNode) toDeleteNode.getSubRight());
            toDeleteNode.setItem(minNodeValue);
            return;
        }

        // 删除只有一颗子树的节点
        if (Objects.nonNull(toDeleteNode.getSubLeft())) {
            // 要删除的结点有左子结点
            if (Objects.nonNull(toDeleteParentNode)) {
                if (nodeValue == toDeleteParentNode.getSubLeft().getItem()) {
                    // 待删除节点是父节点的左子结点
                    toDeleteParentNode.setSubLeft(toDeleteNode.getSubLeft());
                } else {
                    // 待删除节点是父节点的右子结点
                    toDeleteParentNode.setSubRight(toDeleteNode.getSubLeft());
                }
            } else {
                rootNode = (BinarySortNode) toDeleteNode.getSubLeft();
            }
            return;
        }

        // 要删除的结点有右子结点
        if (Objects.nonNull(toDeleteParentNode)) {
            if (nodeValue == toDeleteParentNode.getSubRight().getItem()) {
                // 待删除节点是父节点的左子结点
                toDeleteParentNode.setSubLeft(toDeleteNode.getSubRight());
            } else {
                // 待删除节点是父节点的右子结点
                toDeleteParentNode.setSubRight(toDeleteNode.getSubRight());
            }
        } else {
            rootNode = (BinarySortNode) toDeleteNode.getSubRight();
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (Objects.isNull(rootNode)) {
            System.out.println("二叉排序树为空，不能遍历");
            return;
        }

        rootNode.midOrder();
    }

    /**
     * 根据节点值查找节点
     *
     * @param nodeValue 节点值
     * @return 节点
     */
    public BinarySortNode search(int nodeValue) {
        if (Objects.isNull(rootNode)) {
            return null;
        }
        return rootNode.search(nodeValue);
    }

    /**
     * 根据节点值查找父节点
     *
     * @param nodeValue 节点值
     * @return 父节点
     */
    public BinarySortNode searchParent(int nodeValue) {
        if (Objects.isNull(rootNode)) {
            return null;
        }
        return rootNode.searchParentNode(nodeValue);
    }

    /**
     * 查询并删除指定节点下面最小节点的值
     *
     * @param node 指定节点
     * @return 最小节点的值
     */
    public Integer searchAndDeleteMinSubNodeValue(BinarySortNode node) {
        //循环的查找左子节点，就会找到最小节点
        while (Objects.nonNull(node.getSubLeft())) {
            node = (BinarySortNode) node.getSubLeft();
        }
        // 删除最小结点
        delete(node.getItem());

        return node.getItem();
    }

}
